
% ****************************************************************
%
%   Modeling the Market Checkpoint scenario
%
% ****************************************************************

\section{Target Problem and Method}
\label{sec:Model}

\subsection{Problem Definition}
\label{sec:Problem}
The aim of this work is to find routing paths for wireless sensor network in 2D area, such that the intrusion probability is minimized, connectivity between source nodes and a base station(sink node) is satisfied, and having minimal hop counts between the source node and sink node. Minimizing intrusion probability and connectivity is used for sending critical data and preventing any data loss, while minimal hop counts provide least amount of energy consumption for the wireless sensor network.

Intrusion probability between a pair of sensor nodes are governed by probability of intruders to take position between the two nodes. Intrusion probability of a path from source node to sink node is found by subtracting the probability of sending data from the source node to sink without data loss from the total probability of 1. Intrusion probabilities of a WSN is the average of all intrusion probabilities of all the routes used for communication in the WSN.

Connectivity of a WSN is governed by the allowed routes and communication radii between the sensor nodes. In graph theoretical definition of wireless sensor network. A graph is said to be connected if there is a path between any vertex (node) to any other vertex, such that vertices in the graph represents sensor nodes and sink node(s) and edges between a pair of vertices represent a communication link between the two corresponding nodes in the network.  For network analysis, network graphs usually have heterogeneous nodes such that source nodes, sink nodes or actor nodes. A WSN is said to be connected if from every source nodes, there is at least one communication route to send data to the sink node. The WSN is \emph{k-connected} if the network is tolerant to \emph{k} node failures. In other words, if the smallest number of vertices in the graph, whose removal disconnects the graph is equal to \emph{k}. \emph{k-connectivity} is an objective for WSN design as it corresponds to the robustness of a network.

For modeling energy consumption of the WSN, we assume all source nodes become active at the same time, sense their environment, send data to the sinks or receive data from other nodes. For simplicity, we assume each node consumes same amount of energy so that the lifetime of the nodes are the same. We evaluate energy of a WSN as the difference between total energy of sensor nodes in the WSN and total energy consumed by the sensor nodes.

\subsection{Neuroevolution Approach}
\label{sec:Approach}
For solving the problem defined in the previous subsection, we used a genetic algorithms-based approach. Genetic Algorithms (GAs) are optimizing search techniques based on the principles of natural selection and survival of the fittest. Figure~\ref{NeuroevolutionFigure} shows the creation of a population of genetic neural networks encodings (genotypes). At each iteration of evolution (generation), each genotype is decoded into a neural network (phenotype), which is evaluated in the task, resulting in a fitness value for the genotype. Crossover and mutation among the genotypes with the highest fitness is then used to generate the next generation.

\begin{figure}
\centering
\includegraphics[width=3.5in]{Figures/Neuroevolution}
\caption{Evolving Artificial Neural Networks\cite{Miikkulainen-2010-Neuroevo}.}
\label{NeuroevolutionFigure}
\end{figure}

 The neuroevolutionary approach we used for solving the problem is NeuroEvolution of Augmented Topologies (NEAT) ~\cite{Stanley-2002-Augmenting}, as a genetic algorithm that uses \emph{direct encoding}, where each gene encodes a specific piece of the Artificial Neural Network (ANN), either a node or a connection between nodes. Figure~\ref{NEATGenomeANN} shows an example mapping from genotype(genome) to phenotype(network). In this figure, a genotype is depicted that produces the shown phenotype. There are three input nodes, one hidden, and one output node, and six connection definitions, one of which is recurrent. The third gene is disabled, so the connection that it specifies (between nodes 2 and 5) is not expressed in the phenotype.


\begin{figure}
\centering
\includegraphics[width=3.5in]{Figures/Genome_Network}
\caption{An example mapping of genotype to phenotype \cite{Stanley-2002-Augmenting}.}
\label{NEATGenomeANN}
\end{figure}

We define a communication path in the wireless sensor network as a genome composed of edges that represent communication links between pairs in the network. Genes represent these communication links. Each gene is characterized by two nodes and the direction of the communication between the two nodes. For instance, if a node \emph{A} sends data directly to another node \emph{B}, in a communication path (genome) \emph{P}, the genome contains the gene [\emph{A,B}]. A direct encoding from genome to the phenotype (ANN) is employed using the NEAT architecture.

The population starts from a canonical genome, where all organisms are derived by perturbations on the original genome, and the population speciation is done using a compatibility metric. After this step, each organism is assigned a fitness score within its species. Truncation selection is done on the whole population to remove the individuals with lowest fitness scores, that are not convenient for reproduction step. Reproduction is done by crossover and mutation operations on the individuals in order to replace old generation with a new generation. The new generation speciation is done and this process continues iteratively.
% compatiblity function may be explained
The fitness score of a genome (communication path) is evaluated by the connection status between the source and sink node (if the path is connected or not), intrusion probability of the path and hop counts between the source node and sink node. In this case, hop counts is equal to the number of genes in a genome. There are more than one solutions, since for each sensor node, there should be a communication path from that node to the base station. If the source node and the sink node is not connected in graph, a solution does not exist for the source node. This is not the case for a connected graph and there is a solution for every possible source-sink pair.

